package algorithm_demo.demo_advanced;

import java.util.Arrays;

/**
 *
 * 1. 改写快速排序的方法
 *
 *  * 快速排序 (Quick Sort)快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。
 *  * 不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。
 *  * 但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。
 *  * <p>
 *  * 快速排序的基本思想：
 *  * 通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。
 *  * # 算法步骤快速排序使用分治法open in new window（Divide and conquer）策略来把一个序列分为较小和较大的 2 个子序列，然后递回地排序两个子序列。
 *  * <p>
 *  * 具体算法描述如下：
 *  * 1. 从序列中随机挑出一个元素，做为 “基准”(pivot)；
 *  * 2. 重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *  * 3. 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。
 *  * <p>
 *  * 算法分析
 *  * 稳定性 ：不稳定
 *  * 时间复杂度 ：最佳：O(nlogn)， 最差：O(N^2)，平均：O(nlogn)
 *  * 空间复杂度 ：O(nlogn)
 *  *
 * > 2. bfprt算法
 *
 * @author Api
 * @date 2023/3/27 22:31
 */
public class Code09_QuickSort {

    public static int partition1(int[] arr, int low, int high) {
        int pivot = arr[high];//选择最后一位
        int pointer = low;
        for (int i = low; i < high; i++) {
            if (arr[i] <= pivot) {
                int temp = arr[i];
                arr[i] = arr[pointer];
                arr[pointer] = temp;
                pointer++;
            }
        }
        //这部分代码的意思是将上述遍历后的符合的pointer和最后的基准值交换。
        int temp = arr[pointer];
        arr[pointer] = arr[high];
        arr[high] = temp;
        return pointer;
    }

    /*快速排序算法 1*/
    public static void quickSort1(int[] arr, int low, int high) {
        if (low < high) {
            int position = partition1(arr, low, high);
            quickSort1(arr, low, position - 1);
            quickSort1(arr, position + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 2, 1, 34, 2};//给定一个数组
        quickSort1(arr, 0, arr.length-1); //的带排序后的数组
        System.out.println(Arrays.toString(arr));//打印输出得到数组
    }

    /*快速排序算法 2*/
    public static void quickSort2(int[] arr, int L, int R){
        if (L<R){
            //随机，等概率事件，时间复杂度为N*logN
            swap(arr, L+(int)(Math.random()*(R-L+1)), R);
            int[] p = partition2(arr, L, R);
            quickSort2(arr, L, p[0]-1);//小于区域
            quickSort2(arr, p[0]+1, R);//大于区域
        }
    }

    public static int[] partition2(int[] arr, int L, int R){
        int less = L-1;//小于区域边界
        int more = R;//大于区域边界
        while(L<more){//L表示当前数的位置 arr[R] -> 划分值
            if (arr[L] < arr[R]){//当前数<划分值
                swap(arr,++less, L++);
            }else if (arr[L]> arr[R]){//当前数>划分值
                swap(arr, --more, L);
            }else{
                L++;
            }
        }
        swap(arr, more, R);
        return new int[]{less+1, more};
    }

    //位置交换
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
